插入、删除和随机访问都是 O(1) 的容器
class RandomizedSet {
public:
    /** Initialize your data structure here. */

    //插入和删除 O(1) 用哈希表就可以解决
    //问题在于不能支持随机访问
    //所以还需要搭配vector进行使用
    RandomizedSet() 
    {
        srand(time(0));
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) 
    {
        if(_hash.find(val)==_hash.end())
        {
            //不存在
           _v.push_back(val);
           _hash[val]=_v.size()-1;
            return true;
        }
        else
        {
            return false;
        }

    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) 
    {
        if (_hash.find(val) == _hash.end()) 
        {
            return false;
        }
        //用最后一个 _index位置的值去覆盖删除的值
        int index=_v.size()-1;
        _v[_hash[val]]=_v[index];
        _hash[_v[index]]=_hash[val];
        _hash.erase(val);
        _v.pop_back();
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom() 
    {
        int randindex= rand()%_v.size();
        return _v[randindex];
    }
private:
    vector<int>_v;
    unordered_map<int,int> _hash;// -> 数值 在数组中的下标
    //int _index=0;//到哪个下标处了
    

};
